/*
   @Copyright:LeetCode
   @Author:   tjyemail
   @Problem:  http://leetcode.com/problems/first-missing-positive
   @Language: C++
   @Datetime: 19-06-06 10:55
   */

class Solution {
public:
	int firstMissingPositive(vector<int>& nums) {
		int n=nums.size();
		bool one=false;
		for(int i=0; i<n && !one; ++i)
			one=nums[i]==1;
		if(!one) return 1;
		nums.push_back(1);  // not overrange
		for(int i=0; i<n; ++i)
			if(nums[i]<=0 || nums[i]>n) nums[i]=1;
		for(int i=0; i<n; ++i){
			const int id=abs(nums[i]);
			nums[id]=-abs(nums[id]);
		}
		for(int i=1; i<n+1; ++i)
			if(nums[i]>0) return i;
		return n+1;
	}
};
